package test;
import java.util.Arrays;

class Solution {
    public int wiggleMaxLength(int[] nums) {
        /**
        题目解析：
            由题可得，我们需要找到最长摆动子序列的长度，那么如何去确定是最长摆动子序列呢？
            若是想要当前子序列为最长百度子序列，则要求上一级子序列也为最长摆动子序列
            故本体可以使用动态规划的方式进行解决
        状态表示：
            f[i] 表示，以i下标元素为结尾的所有子序列中，状态为下降，此时最长摆动子序列的长度
            g[i] 表示，以i下标元素为结尾的所有子序列中，状态为上升，此时最长摆动子序列的长度
        状态转移方程：
            
            for(int j = i-1; j >= 0; j++) {
                //f[i],此时下降，最长长度
                if(nums[i] < nums[j] && f[i] < g[j] + 1) {
                    f[i] = g[j] + 1;
                }
                //g[i]，此时上升，最长长度
                if(nums[i] > nums[j] && g[i] < f[j] + 1) {
                    g[i] = f[i] + 1;
                }
            }
        初始化：
            若是初始化第一个，循环不会进去
            为了减少赋值操作，我们将dp表全部设置为最长状态，也就是1
            0无需进行特殊处理，因为此处仅要求差值为正负数交替出现，且差值不能为0，并未说值不能为0
        填表顺序：
            从左至右
        返回值：
            返回两种状态的最大值
        */
        // 预处理
        int n = nums.length;
        // -- 特判：差值不能为0
        if(n == 1 && nums[0] == 0) return 0;
        // 1.创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        // 2.初始化
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        // 3.填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = (i-1); j >= 0; j--) {
                //f[i],此时下降，最长长度
                if(nums[i] < nums[j] && f[i] < (g[j] + 1)) {
                    f[i] = g[j] + 1;
                }
                //g[i]，此时上升，最长长度
                if(nums[i] > nums[j] && g[i] < (f[j] + 1)) {
                    g[i] = f[j] + 1;
                }
            }
            if(ret < f[i]) ret = f[i];
            if(ret < g[i]) ret = g[i];
        }
        // 4.返回值
        return ret;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8});
        System.out.println(ret);
    }
}